
"""
5. 最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring/
"""


class Solution:
    """
    寻找最长回文子串
    （1）暴力搜索
    （2）动态规划
    """

    def method1(self, s: str) -> str:
        """
        暴力解法，找到每一个可能子串，比较大小
        时间复杂度：O(n^2),超出时间限制
        空间复杂度：O(1)
        """
        res = ''
        length = 0

        size = len(s)
        for i in range(size):
            for j in range(i+1, size+1):
                if s[i:j] == s[i:j][::-1]:
                    if len(s[i:j]) > length:
                        length = len(s[i:j])
                        res = s[i:j]

        return res

    def method2(self, s: str) -> str:
        """
        动态规划解法：空间换时间
        时间复杂度：O(n^2)
        空间复杂度：O(n^2)
        """
        size = len(s)

        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        # 初始化dp数组，只有一个字符肯定是回文串
        dp = [[False]*size for _ in range(size)]
        for i in range(size):
            dp[i][i] = True

        # 递推开始
        # 先枚举子串长度，必须是从短串开始
        for L in range(2, size + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(size):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1  # s[i...j]
                # 如果右边界越界，就可以退出当前循环
                if j >= size:
                    break

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i < 2:  # 只有两个元素
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i

        return s[begin:begin+max_len]

    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        return self.method2(s)


def test():
    obj = Solution()
    # s = "babad"
    s = "aaaa"
    res = obj.longestPalindrome(s)
    print(res)


if __name__ == "__main__":
    test()
